#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<vector<int>> ret;
    bool c1[200][200];
    bool c2[200][200];
    int m, n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    void dfs1(vector<vector<int>>& heights, int i, int j)
    {
        c1[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !c1[x][y] && heights[x][y] >= heights[i][j])
            {
                dfs1(heights, x, y);
            }
        }
    }
    void dfs2(vector<vector<int>>& heights, int i, int j)
    {
        c2[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !c2[x][y] && heights[x][y] >= heights[i][j])
            {
                dfs2(heights, x, y);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(); n = heights[0].size();
        int col;
        for (col = 0; col < n; col++)
        {
            dfs1(heights, 0, col);
        }
        int row;
        for (row = 0; row < m; row++)
        {
            dfs1(heights, row, 0);
        }
        for (col = 0; col < n; col++)
        {
            dfs2(heights, m - 1, col);
        }
        for (row = 0; row < m; row++)
        {
            dfs2(heights, row, n - 1);
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (c1[i][j] && c2[i][j])
                {
                    ret.push_back({ i,j });
                }
            }
        }
        return ret;
    }
};


// class Solution {
// public:
//     int m,n;
//     int dx[4] = {0,0,1,-1};
//     int dy[4] = {1,-1,0,0};
//     void dfs(vector<vector<int>>& heights,int i, int j, vector<vector<bool>>& vis)
//     {
//         vis[i][j] = true;
//         for(int k = 0; k < 4; k++)
//         {
//             int x = i + dx[k];int y = j + dy[k];
//             if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && heights[x][y] >= heights[i][j])
//             {
//                 dfs(heights,x,y,vis);
//             }
//         }
//     }

//     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//         m = heights.size();n = heights[0].size();
//         vector<vector<int>> ret;
//         vector<vector<bool>>vis1(m,vector<bool>(n));
//         vector<vector<bool>>vis2(m,vector<bool>(n));
//         int col;
//         for(col = 0; col < n; col++)
//         {
//             dfs(heights,0,col,vis1);
//         }
//         int row;
//         for(row = 0; row <m; row++)
//         {
//             dfs(heights,row,0,vis1);
//         }
//         for(col = 0; col < n; col++)
//         {
//             dfs(heights,m - 1,col,vis2);
//         }
//         for(row = 0; row <m; row++)
//         {
//             dfs(heights,row,n - 1,vis2);
//         }
//         for(int i = 0; i < m; i++)
//         {
//             for(int j = 0; j < n; j++)
//             {
//                 if(vis1[i][j] && vis2[i][j])
//                 {
//                     ret.push_back({i,j});
//                 }
//             }
//         }
//         return ret;
//     }
// };
// class Solution {
// public:
//     int m,n;
//     int dx[4] = {0,0,1,-1};
//     int dy[4] = {1,-1,0,0};
//     char prev = 'O';
//     void dfs(vector<vector<char>>& board, int i, int j)
//     {
//         board[i][j] = '.';
//         for(int k = 0; k < 4; k++)
//         {
//             int x = i + dx[k];
//             int y = j + dy[k];
//             if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == prev)
//             {
//                 dfs(board,x,y);
//             }
//         }
//     }
//     void solve(vector<vector<char>>& board) 
//     {
//         m = board.size();
//         n = board[0].size();
//         int col;
//         for(col = 0; col < n; col++)
//         {
//             if(board[0][col] == 'O')
//                 dfs(board,0,col);
//         } 
//         for(col = 0; col < n; col++)
//         {
//             if(board[m - 1][col] == 'O')
//                 dfs(board,m - 1,col);
//         } 
//         int row;
//         for(row= 0; row < m; row++)
//         {
//             if(board[row][0] == 'O')
//                 dfs(board,row,0);
//         }
//         for(row= 0; row < m; row++)
//         {
//             if(board[row][n - 1] == 'O')
//                 dfs(board,row,n-1);
//         }

//         // for(int i = 0; i < m; i++)
//         // {
//         //     for(int j = 0; j < n; j++)
//         //     {
//         //         cout << board[i][j] << " ";
//         //     }
//         //     cout << endl;
//         // }
//         for(int i = 0; i < m; i++)
//         {
//             for(int j = 0; j < n; j++)
//             {
//                 if(board[i][j] == '.')
//                 {
//                     board[i][j] = 'O';
//                 }
//                 else if(board[i][j] == 'O')
//                 {
//                     board[i][j] = 'X';
//                 }
//             } 
//         }
//     }
// };


class Solution {
public:
    int m, n;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    char prev = 'O';
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '.';
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == prev)
            {
                dfs(board, x, y);
            }
        }
    }
    void solve(vector<vector<char>>& board)
    {
        m = board.size();
        n = board[0].size();
        int col;
        for (col = 0; col < n; col++)
        {
            if (board[0][col] == 'O')
                dfs(board, 0, col);
            if (board[m - 1][col] == 'O')
                dfs(board, m - 1, col);
        }

        int row;
        for (row = 0; row < m; row++)
        {
            if (board[row][0] == 'O')
                dfs(board, row, 0);
            if (board[row][n - 1] == 'O')
                dfs(board, row, n - 1);
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == '.')
                {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
};
class Solution {
public:
    int m, n;
    int ret = 0;
    bool check[300][300];
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == '1')
            {
                check[x][y] = true;
                dfs(grid, x, y);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(); n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!check[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    check[i][j] = true;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
};
class Solution {
public:
    int path = 0, ret = 0;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m, n;
    vector<vector<bool>> check;
    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        check[i][j] = true;
        path++;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k]; int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
        }
    }
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        m = grid.size(); n = grid[0].size();
        check = vector<vector<bool>>(m, vector<bool>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!check[i][j] && grid[i][j] == 1)
                {
                    dfs(grid, i, j);
                    ret = max(ret, path);
                    path = 0;
                }
            }
        }
        return ret;
    }
};

class Solution {

public:
    int c;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m;
    int n;
    int scol;
    void dfs(vector<vector<int>>& image, int sr, int sc)
    {
        image[sr][sc] = c;
        for (int k = 0; k < 4; k++)
        {
            int x = sr + dx[k];
            int y = sc + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && scol == image[x][y])
            {
                dfs(image, x, y);
            }
        }

    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if (color == image[sr][sc])
            return image;
        c = color;
        m = image.size();
        n = image[0].size();
        scol = image[sr][sc];
        dfs(image, sr, sc);
        return image;
    }
};